package ar.uba.tleng.g99.expregs.automata;

import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;

/**
 * Automata deterministico (AFD).
 * 
 * @author g99
 */
public final class AutomataD {

	private final NodeD initialNode;
	private final Set<NodeD> finalNodes;
	private final Set<Character> sigma;

	public AutomataD(Set<Character> sigma, NodeD initial, Set<NodeD> finals) {
		this.sigma = sigma;
		this.initialNode = initial;
		this.finalNodes = new HashSet<NodeD>(finals);
	}

	private static Set<Node> lambdaClosure(Node node) {
		Set<Node> closure = new HashSet<Node>();
		Set<Node> toProcess = new HashSet<Node>();
		toProcess.add(node);
		while (!toProcess.isEmpty()) {
			Node n = toProcess.iterator().next();
			toProcess.remove(n);
			if (closure.contains(n)) {
				continue;
			}
			Set<Node> lambdas = n.childs.get(Node.LAMBDA);
			if (lambdas != null) {
				toProcess.addAll(lambdas);
			}
			closure.add(n);
		}
		return closure;
	}

	private static AutomataND removeLambdas(AutomataND afnd) {
		NodeCopier nc = new NodeCopier(afnd.getInitialNode());
		Node newInitial = nc.translate(afnd.getInitialNode());
		Set<Node> processed = new HashSet<Node>();
		Set<Node> toProcess = new HashSet<Node>();
		toProcess.add(afnd.getInitialNode());
		Set<Node> oldFinals = afnd.getFinalNodes();
		Set<Node> newFinals = new HashSet<Node>();
		while (!toProcess.isEmpty()) {
			Node n = toProcess.iterator().next();
			toProcess.remove(n);
			if (processed.contains(n)) {
				continue;
			}
			Node n2 = nc.translate(n);
			Set<Node> closure = lambdaClosure(n);
			boolean isFinal = false;
			for (Node c : closure) {
				n2.mergeChilds(nc.translate(c));
				if (oldFinals.contains(c)) {
					isFinal = true;
				}
			}
			n2.childs.remove(Node.LAMBDA);
			if (isFinal) {
				newFinals.add(n2);
			}
			for (Entry<Character, Set<Node>> e : n.childs.entrySet()) {
				toProcess.addAll(e.getValue());
			}
			processed.add(n);
		}
		return new AutomataND(afnd.getSigma(), newInitial, newFinals);
	}

	/**
	 * Devuelve un nuevo AFD equivalente al AFND dado.
	 * 
	 * @param afnd
	 *            el automata no deterministico.
	 * @return el automata deterministico equivalente.
	 */
	public static AutomataD fromAFND(AutomataND afndlambdas) {
		AutomataND afnd = removeLambdas(afndlambdas);
		// Translation table for new states
		Map<Set<Node>, NodeD> table = new HashMap<Set<Node>, NodeD>();

		NodeD initial = createTableOfNewNodes(
				Collections.singleton(afnd.getInitialNode()), table);
		Set<NodeD> finals = new HashSet<NodeD>();
		Set<Node> oldFinals = afnd.getFinalNodes();
		for (Entry<Set<Node>, NodeD> e : table.entrySet()) {
			Set<Node> intersection = new HashSet<Node>(e.getKey());
			intersection.retainAll(oldFinals);
			if (intersection.size() > 0) {
				finals.add(e.getValue());
			}
		}
		return new AutomataD(afnd.getSigma(), initial, finals);
	}

	private static NodeD createTableOfNewNodes(Set<Node> nodeSet,
			Map<Set<Node>, NodeD> table) {
		if (table.containsKey(nodeSet)) {
			return table.get(nodeSet);
		}
		NodeD nd = new NodeD();
		Node mergeNode = new Node();
		for (Node n : nodeSet) {
			mergeNode.mergeChilds(n);
		}
		table.put(nodeSet, nd);
		for (Entry<Character, Set<Node>> e : mergeNode.childs.entrySet()) {
			Character c = e.getKey();
			Set<Node> s = e.getValue();
			NodeD dest = createTableOfNewNodes(s, table);
			nd.addTransition(c, dest);
		}		
		return nd;
	}

	public NodeD getInitialNode() {
		return initialNode;
	}

	public Set<NodeD> getFinalNodes() {
		return finalNodes;
	}

	public Set<Character> getSigma() {
		return Collections.unmodifiableSet(sigma);
	}

}